export function fastSort(
    leftIndex: number, // 头部指针
    rightIndex: number, // 尾部指针
    arr: number[] // 原数组
): number[] {
    // 如果开始位置大于结束位置，表示遍历已结束
    if (leftIndex > rightIndex) return [];
    // 设置中位数，默认为数组第一个数
    const midNum = arr[leftIndex];
    // 设置默认检索的开始/结束位置
    let i = leftIndex;
    let j = rightIndex;
    // 末尾检索的位置大于从头检索的位置时继续检索
    while (j > i) {
        // 优先移动末尾的指针，直到找到小于中位数的值
        while (midNum <= arr[j] && i < j) {
            j--;
        }
        // 然后移动头部指针，直到找到大于中位数的值
        while (midNum >= arr[i] && i < j) {
            i++;
        }
        // 头部指针位置小于尾部指针，交换两个数
        if (i < j) {
            const temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 最后交换最后位置与中位数的位置的数
    const small = arr[i];
    arr[i] = arr[j];
    arr[j] = small;
    // console.log("j: %s, i: %s, arr: %s", j, i, arr);

    // 递归前半部分数组
    fastSort(leftIndex, i - 1, arr);
    // 递归后半部分数组
    fastSort(i + 1, rightIndex, arr);
    return arr;
}

const testArr = [0, 0, 0, 0];
console.log("fastSort:", fastSort(0, testArr.length - 1, testArr));
